package java学习.代码随想录.动态规划;

import javax.print.attribute.standard.MediaSize;
import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/2 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 买卖股票的最佳时机II {
    /**
     * 1.dp[i]  前 i 天 (第i天卖出 ) 的获取最大总利润。
     * 我算是发现了，规律就是推的。
     */

    /**      找规律过程：从下往上想比较顺
     *                    0 1 2 3 4 5
     *     输入：prices = [7,1,5,3,6,4]       输出：7
     *          dp[i]           dp[i-1]+p[i] - min(i-1 ~ i )
     *     即   dp[i-1]+p[i] - min(p[i],p[i-1])
     *
     *      dp[0] =0   dp[1] =0   dp[2] =4   dp[3] =4    dp[4] = 4+3=7    dp[5] = 7
     *                                                  同一天可卖出买入
     *   dp[3]:   dp[2] = 4.  此时 还有 p[3], 考虑在 p[3] 之前选个 <p[3]的值买入。即：min(p[3],p[2])
     *      dp[3] = dp[2] +p[3]-min[2~3]
     *
     *      dp[4] =dp[3]+ p[4]-min[3~4] = 7
     *
     *      dp[4] = dp[3] + p[4]-min()
     *
     *      dp[5] = dp[4] + p[5]-min(4,5)
     */


    /**               0 1 2 3 4
     * 输入：prices = [1,2,3,4,5]
     *  输出：4
     *  dp[0] = 0; dp[1] = 1 dp[2] = 2 dp[3] = 3 dp[4] = 4
     *  dp[1] = dp[0]+p[1]- min(p[0],p[1]) = 1;
     *  dp[2] = dp[1] +p[2]- min(p[2],p[1]) = 1+3-2 = 2
     *  dp[3] = 2+ 4-3 = 3
     *  dp[4] = 3 + 5-4 = 4;
     *                 0 1 2 3 4
     *  输入：prices = [7,6,4,3,1]
     *  输出：0
     *  dp[0] = 0; dp[1] = 0 dp[2] = 0 dp[3] = 0 dp[4] = 0
     *  dp[2] = dp[1] +p[2]- min(p[2],p[1]) = 0 + 4-4 = 0
     *
     */

    public static int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n];

        for (int i = 1; i < n; i++) {
          dp[i]  = dp[i-1]+prices[i] - Math.min(prices[i],prices[i-1]);
        }
        System.out.println(Arrays.toString(dp));
        return dp[n-1];
    }

    /**
     * 定义：
     *      dp[i][0] 第 i天 卖出（不持有）股票的最大利润
     *      dp[i][1] 第i 天 持有股票的最大利润    (持有不一定就是卖出，也可以不卖出)
     * 公式：
     *                            之前就卖出了 ,      之前仍持有，现在卖出
     *      dp[i][0] = Math.max(dp[i-1][0],       dp[i-1][1] + prices[i]);
     *
     *                            之前就没卖出(持有) ,  之前已经卖出 ，现在买入（可能成负数  ）
     *      dp[i][1] = Math.max(dp[i-1][1],        dp[i-1][0] - prices[i]);
     *
     * 初始化： dp[0][0] = 0;
     *        dp[0][1] = -price[i];  第0天持有股票，说明第0天买入了。
     *
     */
    public static int maxProfit1(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
        }

        for (int i = 0; i < n; i++) {
            System.out.println(dp[i][0] +" "+ dp[i][1]);
        }

//        return Math.max(dp[n-1][1],dp[n-1][0]);
        return  dp[n-1][0];

    }

        public static void main(String[] args) {

//        输入：[7,1,5,3,6,4]
//        输出：7
        int []test = {7,1,5,3,6,4};
        System.out.println(maxProfit(test));
        System.out.println(maxProfit1(test));
    }
}
